/*
 * @lc app=leetcode.cn id=86 lang=swift
 *
 * [86] 分隔链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        let dummy1 = ListNode(-1)
        let dummy2 = ListNode(-1)
        var p1: ListNode? = dummy1
        var p2: ListNode? = dummy2
        var p = head
        while p != nil {
            if p!.val < x {
                p1?.next = p
                p1 = p1?.next
            } else {
                p2?.next = p
                p2 = p2?.next
            }
            p = p?.next
        }
        // 断开最后的连接 防止成环
        p2?.next = nil
        p1?.next = dummy2.next
        return dummy1.next
    }
}
// @lc code=end

